package com.algrithom.graph.shortestpath;

/**
 * 典型的贪梵算法 单源最短路径
 * 主要解决所有边的权为非负的单源最短路径问题
 * 有向图/无向图+无负权边
 *
 * @author think
 * @version 1.0.0
 * @since 2020/2/12
 */
public class Dijkstra {
    
    public static void main(String[] args){
        int[][] weight = {{0,3,2000,7,9999999},{3,0,4,2,9999999},{9999999,4,0,5,6},{7,2,5,0,4},{9999999,9999999,4,6,0}};
        
        // 从0起点开始到其它所有点的最短距离
        int[] path = dijsktra(weight,0);
        for (int value : path) {
            System.out.print(value + "  ");
        }
    }
    
    public static int[] dijsktra(int[][] weight,int start){
        //接受一个有向图的权重矩阵，和一个起点编号start（从0编号，顶点存在数组中）
        //返回一个int[] 数组，表示从start到它的最短路径长度
        //顶点个数
        int n = weight.length;
        //存放从start到其他各点的最短路径
        int[] shortPath = new int[n];
        //标记当前该顶点的最短路径是否已经求出,1表示已求出
        int[] visited = new int[n];
        
        //初始化，第一个顶点求出
        shortPath[start] = 0;
        visited[start] = 1;
        
        //要加入n-1个顶点
        for (int count = 1; count <= n - 1; count++) {
            //选出一个距离初始顶点start最近的未标记顶点
            int k = -1;
            int dmin = 1000;
            for (int i = 0; i < n; i++) {
                if (visited[i] == 0 && weight[start][i] < dmin) {
                    dmin = weight[start][i];
                    k = i;
                }
            }
            
            //将新选出的顶点标记为已求出最短路径，且到start的最短路径就是dmin
            shortPath[k] = dmin;
            visited[k] = 1;
            
            //以k为中间点想，修正从start到未访问各点的距离
            for (int i = 0; i < n; i++) {
                if (visited[i] == 0 && weight[start][k] + weight[k][i] < weight[start][i]) {
                    weight[start][i] = weight[start][k] + weight[k][i];
                }
            }
        }
        
        return shortPath;
    }
}
